package simpledb.optimizer;

import simpledb.execution.Predicate;

import java.util.Arrays;

/**
 * IntHistogram 类：表示一个基于整型字段的固定宽度直方图。
 *
 * 该类用于统计数据库中某一整数字段的分布情况，并估计某个查询条件的选择率（selectivity）。
 * 选择率是指满足某个谓词操作的元组占总元组的比例，用于优化器进行执行计划选择。
 */
public class IntHistogram implements Histogram<Integer> {

    private int   maxVal;         // 字段最大值
    private int   minVal;         // 字段最小值
    private int[] heights;        // 每个桶的高度（即桶中包含的数据数量）
    private int   buckets;        // 桶的数量
    private int   totalTuples;    // 总共添加了多少条数据
    private int   width;          // 每个桶的宽度（除最后一个桶外）
    private int   lastBucketWidth; // 最后一个桶的宽度

    /**
     * 创建一个新的 IntHistogram。
     *
     * 这个直方图会将传入的整数值划分为 "buckets" 个桶。
     * 值通过 addValue() 方法逐个添加。
     *
     * 实现要求：
     * - 使用常数空间（不能存储所有原始数据）
     * - 时间复杂度与添加的数据量无关（O(1)）
     *
     * @param buckets 要划分的桶的数量
     * @param min 字段的最小可能值
     * @param max 字段的最大可能值
     */
    public IntHistogram(int buckets, int min, int max) {
        this.minVal = min;
        this.maxVal = max;
        this.buckets = buckets;
        this.heights = new int[buckets];

        // 计算每个桶的宽度。注意至少为1
        int total = max - min + 1;
        this.width = Math.max(total / buckets, 1);

        // 最后一个桶的宽度可能是不同的，以覆盖整个区间
        this.lastBucketWidth = total - (this.width * (buckets - 1));
        this.totalTuples = 0;
    }

    /**
     * 添加一个整数值到直方图中。
     *
     * 如果值不在 [minVal, maxVal] 区间内，则忽略。
     *
     * @param v 要添加的整数值
     */
    public void addValue(Integer v) {
        if (v < this.minVal || v > this.maxVal) {
            return;
        }
        int bucketIndex = (v - this.minVal) / this.width;
        if (bucketIndex >= this.buckets) {
            return;
        }
        this.totalTuples++;
        this.heights[bucketIndex]++;
    }

    /**
     * 估计大于给定值的元组比例。
     *
     * @param bucketIndex 所在桶索引
     * @param predicateValue 查询值
     * @param bucketWidth 当前桶的宽度
     * @return 估计的比例
     */
    private double estimateGreater(int bucketIndex, int predicateValue, int bucketWidth) {
        if (predicateValue < this.minVal) {
            return 1.0; // 小于最小值的所有值都大于它
        }
        if (predicateValue >= this.maxVal) {
            return 0; // 大于等于最大值没有值满足
        }

        // 当前桶内的右边界
        int bucketRight = bucketIndex * this.width + this.minVal;

        // 计算当前桶中比 predicateValue 大的部分所占比例
        double bucketRatio = ((double) (bucketRight - predicateValue)) / bucketWidth;
        double result = bucketRatio * (((double) this.heights[bucketIndex]) / this.totalTuples);

        // 统计右边所有桶的总数量
        int sum = 0;
        for (int i = bucketIndex + 1; i < this.buckets; i++) {
            sum += this.heights[i];
        }

        // 返回总比例
        return ((double) sum) / this.totalTuples + result;
    }

    /**
     * 估计等于给定值的元组比例。
     *
     * @param bucketIndex 所在桶索引
     * @param predicateValue 查询值
     * @param bucketWidth 当前桶的宽度
     * @return 估计的比例
     */
    private double estimateEqual(int bucketIndex, int predicateValue, int bucketWidth) {
        if (predicateValue < this.minVal || predicateValue > this.maxVal) {
            return 0;
        }

        // 假设均匀分布：该桶中每个值的平均数量是 height / width
        double result = ((double) this.heights[bucketIndex]) / bucketWidth;
        result /= this.totalTuples;
        return result;
    }

    /**
     * 根据当前直方图估计某个谓词和值的选择率。
     *
     * 例如：如果 op 是 GREATER_THAN 且 v 是 5，
     * 则返回大于 5 的元组占总元组数的比例。
     *
     * @param op 操作符（如 EQUALS、GREATER_THAN 等）
     * @param v 查询值
     * @return 估计的选择率（0.0 ~ 1.0）
     */
    public double estimateSelectivity(Predicate.Op op, Integer v) {
        final int bucketIndex = Math.min((v - this.minVal) / this.width, this.buckets - 1);
        final int bucketWidth = bucketIndex < this.buckets - 1 ? this.width : this.lastBucketWidth;

        double ans;
        switch (op) {
            case GREATER_THAN:
                ans = estimateGreater(bucketIndex, v, bucketWidth);
                break;
            case EQUALS:
                ans = estimateEqual(bucketIndex, v, bucketWidth);
                break;
            case LESS_THAN:
                ans = 1.0 - estimateGreater(bucketIndex, v, bucketWidth) - estimateEqual(bucketIndex, v, bucketWidth);
                break;
            case LESS_THAN_OR_EQ:
                ans = 1.0 - estimateGreater(bucketIndex, v, bucketWidth);
                break;
            case GREATER_THAN_OR_EQ:
                ans = estimateEqual(bucketIndex, v, bucketWidth) + estimateGreater(bucketIndex, v, bucketWidth);
                break;
            case NOT_EQUALS:
                ans = 1.0 - estimateEqual(bucketIndex, v, bucketWidth);
                break;
            default:
                return -1; // 不支持的操作
        }
        return ans;
    }

    /**
     * 获取该直方图的平均选择率。
     *
     * 这个方法不是实现基本连接优化所必需的，
     * 但在实现更高效的优化策略时可能会用到。
     *
     * @return 平均选择率
     */
    public double avgSelectivity() {
        return 1.0; // 默认返回1，可扩展
    }

    /**
     * 调试用 toString 方法，输出当前直方图信息。
     */
    @Override
    public String toString() {
        return "IntHistogram{" + "maxVal=" + maxVal + ", minVal=" + minVal + ", heights=" + Arrays.toString(heights)
               + ", buckets=" + buckets + ", totalTuples=" + totalTuples + ", width=" + width + ", lastBucketWidth="
               + lastBucketWidth + '}';
    }
}
